package paixu;

/**
 * @author lj
 * @Description: 桶排序
 * @date 2020-11-04 12:56
 * @QQ 851477108
 */


public class BucketSort {
    public static void main(String[] args) {
        int[] arr = {5,8,6,2,4,3};
        bucketSort(arr);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }

    public static void bucketSort(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }

        int max = Integer.MIN_VALUE;

        //遍历找到最大值
        for (int i = 0; i < arr.length; i++) {
            max = Math.max(arr[i],max);
        }

        //因为考虑正整数，所以需要max+1个桶，一个桶代表一个数值，并不是范围
        int[] bucket = new int[max + 1];
        // 放数入桶的操作,相同的数放在同一个桶中
        for (int i = 0; i < arr.length; i++){
            bucket[arr[i]]++;
        }

        int i = 0;
        //按序遍历桶即可，桶的计数就是对应数字出现的次数
        for (int j = 0; j < bucket.length; j++) {
            //此while循环输出的是第j个桶存放的数字个j
            while (bucket[j]-->0){
                arr[i++] = j;
            }
        }
    }
}
